1. Field of the Invention
This invention relates to the field of data encoding. More particularly, this invention relates to runlength type data encoding.
2. Description of the Prior Art
Runlength data encoding to achieve data compression is well known. An example of a system including runlength coding is that proposed by the Joint Photographic Experts Group (JPEG) and currently under review by the International Standards Organisation.
The JPEG standard is intended for the compression of image data in computer systems. The image data is transformed into the spatial frequency domain by discrete cosine transformation. The ac spatial components have a distinctly different character to the dc spatial components. The ac spatial components are subject to runlength coding to exploit the long runs of zero values in this data. The dc spatial components do not show this characteristic.
The JPEG standard proposes the use of code words with the following syntax for the ac data, i.e.
[RUNLENGTH, SIZE], [AMPLITUDE] PA1 . . 0,0,0,7,0,0,0,0,0,0,11,0,0,0 . . . PA1 [SIZE], [AMPLITUDE] PA1 (i) an input for feeding input data values in parallel to a zero value detector, an encoded word generator and an encoded word bit length indicator; PA1 (ii) a zero runlength counter and an encoder state machine connected in parallel to the output of said zero value detector; and PA1 (iii) an encoded data store; PA1 (i) feeding input data values in parallel to a zero value detector, an encoded word generator and an encoded word bit length indicator; PA1 (ii) coupling a zero runlength counter and an encoder state machine in parallel to the output of said zero value detector; and PA1 (iii) under control of said encoder state machine, receiving and storing into an encode data store zero runlength values from said zero runlength counter, encoded word bit length values from said encoded word bit length indicator and encoded words from said encoded word generator.
In this case RUNLENGTH is the number of zeros preceding a non-zero value. SIZE is the number of bits that will be needed to represent the non-zero value. AMPLITUDE is the non-zero value and has a bit length equal to that specified by SIZE.
Consider the following data stream of image data,
The middle portion, comprising six zeros followed by a non-zero value of 11, would be encoded with the value of RUNLENGTH=6. The non-zero value of 11 will require four bits to represent it, and so SIZE=4. The value of AMPLITUDE is 11, or 1011 in binary. Thus, the sequence 0,0,0,0,0,0,11 is encoded as [6,4], [11].
The JPEG standard proposes the use of code words with the following syntax for the dc data, i.e.
Each data value is encoded separately with SIZE being equal to the number of bits needed to represent the value and AMPLITUDE being the value itself. A dc data value of 5 would require three bits to represent and so SIZE=3. AMPLITUDE would then equal 5 or 101 in binary.
Whilst the JPEG standard gives a full description of the encoding format to be used, it does not indicate how such encoding could be achieved in practice. The problems of carrying out the encoding in the non-real time image display systems of the computers for which the JPEG standard is primarily intended are not too great. In a computer system the data can be read into memory and then scanned to identify the RUNLENGTH and SIZE values as a separate operation.
The manner in which the coding can be achieved in a real time video system is less straightforward. The overall data rate in a video system requires the processing of about sixty fields of image data every second to keep pace with the video display. Using a computer system operating under the control of encoding software would not be fast enough to keep pace with this data rate and would be an expensive solution in a situation which does not require the other facilities afforded by the computer system.